/**
 * Created with IntelliJ IDEA.
 * User: yanshiyi
 * Date: 13-11-26
 * Time: 下午8:23
 * To change this template use File | Settings | File Templates.
 */
package collections

type Stack interface {

	Push(value interface {})
	Pop() (value interface {})
	Size() int
}

type Element struct {
	value interface {}
	next *Element
}

type LinkStack struct {
	top *Element
	size int
}

func (this LinkStack) Size() int {
	return this.size
}

func (this *LinkStack) Push(value interface{}) {
	this.top = &Element{value, this.top}
	this.size += 1
}

func (this *LinkStack) Pop() (value interface {}) {
	if this.size > 0 {
		value, this.top = this.top.value, this.top.next
		this.size -= 1
	}
	return
}

type ArrayStack struct {
	elements []interface {}
	topIndex int
}

func (this *ArrayStack) Push(value interface {}) {
	this.elements = append(this.elements, value)
	this.topIndex += 1
}

func (this *ArrayStack) Pop() (value interface {}) {

	if this.topIndex > 0 {
		value = this.elements[this.topIndex - 1]
		this.topIndex -= 1
	}

	if this.topIndex < len(this.elements)/2 {
		this.elements = this.elements[:this.Size()]
	}
	return
}

func (this ArrayStack) Size() int {
	return this.topIndex
}




